import {inOrder} from "../MyClass/Tree.js";
import {buildBinarySearchTree} from "../MyClass/BinarySearchTree.js";
import TreeNode from "../MyClass/BinarySearchTree.js";

let arr = [1, 5, 8, 3, 7, 10, 22, 6, 9, 0]
let root = buildBinarySearchTree(arr)
/*
             1
            / \
           0   5
              / \
             3   8
                / \
               7  10
              /   / \
             6   9  22
* */
let inOrderList = inOrder(root)
console.log(inOrderList.join(" "));

function checkHeight(node) {
    //空结点高度为0
    if (node === null) return 0
    //递归计算左右子树高度
    let leftHeight = checkHeight(node.left)
    if (leftHeight === -1) { //提前返回
        return -1
    }
    let rightHeight = checkHeight(node.right)
    if (rightHeight === -1) {
        return -1
    }
    //高度差太大，不平衡，返回-1
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1
    }
    //返回左右子节点中高的值
    return Math.max(leftHeight, rightHeight) + 1 //父节点也要算一层
}

function isBalanced(root) {
    return checkHeight(root) !== -1
}


// let arr2 = [10,5,15,3,7,12,20];
// let balanceTree=buildBinarySearchTree(arr2)
// /*
//          10
//         /  \
//        5    15
//       / \   / \
//      3   7 12 20
//
// * */
// console.log(inOrder(balanceTree).join(" "));
// console.log(isBalanced(root));
// console.log(isBalanced(balanceTree));


/**
 * 左单旋
 * @param {TreeNode} root - 要旋转的树
 * @param {Number} pivotValue - 要旋转的节点对应的值
 */
function leftRotation(root, pivotValue) {
    let pivot = root

}